package iotree;

/**
 * @Author Fizz Pu
 * @Date 2021/5/8 下午7:12
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */


import com.sun.source.tree.Tree;

import java.util.Deque;
import java.util.*;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */


class Codec {

    static private class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {

        if(root == null){
            return "[]";
        }

        // arrayDeque本身不能添加null的元素
        List<Integer> resultArray = new ArrayList<>();
        Deque<TreeNode> arrayDeque = new LinkedList<>();
        TreeNode currentNode = root ;
        arrayDeque.addLast(currentNode);
        while (!arrayDeque.isEmpty()) {
            currentNode = arrayDeque.removeFirst();

            if (currentNode != null) {
                arrayDeque.addLast(currentNode.left);
                arrayDeque.addLast(currentNode.right);
            }

            if (currentNode == null) {
                resultArray.add(null);
            }

            if (currentNode != null) {
                resultArray.add(currentNode.val);
            }

        }

        int len = resultArray.size();
        String str = "";
        boolean isStart = false;
        for(int i = len - 1; i >= 0; i--){
            Integer ele = resultArray.get(i);

            if(!isStart && ele != null){
                isStart = true;
            }

            if(isStart){
                if(ele == null){
                    str = "null," + str;
                } else {
                    str = ele + "," + str;
                }
            }
        }

        str = "[" + str.substring(0, str.length() - 1) + "]";
        return str;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.equals("[]")){
            return null;
        }

        String seq = data.substring(1, data.length() - 1);
        String[] strings = seq.split(",");
        Deque<TreeNode> deque = new LinkedList<>();
        int index = 1;
        int len = strings.length;
        boolean isLeft = true;
        TreeNode root = new TreeNode(Integer.parseInt(strings[0]));
        TreeNode current = root;

        while (index < len){
            String tmp = strings[index];
            if(!tmp.equals("null")){
                int val = Integer.parseInt(tmp);
                TreeNode treeNode = new TreeNode(val);
                if(isLeft){
                    current.left = treeNode;
                } else {
                    current.right = treeNode;
                }
                deque.addLast(treeNode);
            }
            isLeft = !isLeft;
            index++;

            // 一圈
            if(isLeft){
                current = deque.removeFirst();
            }
        }

        return root;
    }

    public static void main(String[] args) {
        Codec codec = new Codec();
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;
        TreeNode root = node1;

        System.out.println(codec.deserialize(codec.serialize(root)));
    }

}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
